// https://leetcode.cn/problems/unique-paths-ii/

// 算法思路总结：
// 1. 使用滚动数组优化空间复杂度
// 2. 初始化第一行路径数，遇到障碍物提前终止
// 3. 状态转移：无障碍时dp[j] += dp[j-1]，有障碍时清零
// 4. 时间复杂度：O(m×n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<int> dp(n + 1, 0);

        for (int i = 1 ; i <= n ; i++)  
            if (obstacleGrid[0][i - 1] == 0)
                dp[i] = 1;
            else break;

        for (int i = 1; i < m ; i++)
        {
            for (int j = 1 ; j <= n ; j++)
            {
                if (obstacleGrid[i][j - 1] == 1)
                    dp[j] = 0;
                else dp[j] = dp[j] + dp[j - 1];
            }
        }

        return dp[n];
    }
};

int main()
{
    vector<vector<int>> vv1 = {{0,0,0}, {0,1,0}, {0,0,0}};
    vector<vector<int>> vv2 = {{0,1}, {0,0}};

    Solution sol;

    cout << sol.uniquePathsWithObstacles(vv1) << endl;
    cout << sol.uniquePathsWithObstacles(vv2) << endl;

    return 0;
}